package my.algorithms.mcorrea.topcoder;

import java.util.HashMap;
import java.util.Map;

/**
 *http://community.topcoder.com/stat?c=problem_statement&pm=7278
 * @author mcorrea
 */
public class GoodExhibition {

    public static void main(String[] args) {
		System.out.println( numberOfPictures(new String[]{"picture"}, 100)  );
		System.out.println( numberOfPictures(new String[]{"picture", "canvas"}, 2)  );
		System.out.println( numberOfPictures(new String[]{"picture", "canvas", "picture", "canvas", "picture"}, 2)  );
		System.out.println( numberOfPictures(new String[]{"picture", "canvas", "picture", "canvas", "picture"}, 3)  );
		System.out.println( numberOfPictures(new String[]{"a","a","A","a","A","A"}, 3)  );
		
		System.out.println( numberOfPictures(new String[]{"pRUiTKgJUEeSFbWUxeEskVkfdqiSbrlfMCTtdOWfbP", "woDwzTMBSfbLWmUACrhKqNwpShhbJgVTFOiC", "mkANTrOMNYdFZtKpkXevnBxhqUesiXqzMRnNaEfrJiAyIOcEia", "MxmJTyMJdeUJdhKOUEnWbwnDdoOUMEjNtXOnt", "hEfbskQZptmNIvWESjTvvfOMxdVTjAH", "WOlaNFWaaHrNXzGpHbGQShWz", "GDbP", "cIxTPlixXJLhBAqNvllRkJlMtCYoRnwzPVLTkhnGLevbGwdjhC", "MatdXwrnzLdY", "ykiOWMndrSZrwLOBWzzTmkQitvFTDnjmFBKhEziOlhPhj", "TTDO", "WxbTqvPOGHRFgolfEMWFuijrfduy", "gIXcPsuNTHOgdXg", "KllkDskMgadpwuhLyhKkGQWPLzFpLnkLyvd", "KTQcJskKAfQlTtyAhPrgAt", "AlrjGGvdnPmABJlvbXZLvZmm", "mctdP", "X", "rNpYmZylxTucRuSSpccwg", "IlAtTKgPlfhnehUgsHIBFHPvDv", "EbvmJLPjFTYpmyKjVqlyPlehGhdwzcKA", "SKDUelYEYjkigcbDeqGGjYeVtVaqcXPZTNHpj", "VdMdqMftef", "elcBJmGfvZ", "oAxQgOaHUBpuiZYMNXBjfNQUzJaWsKvhcEUsrVaePQyE", "TimOCwHrAhkWJGjYyZnEQcZGuSgxuQJByBmIoHtSNC", "crpSiGZfAIknHxMVlmGGpgSFNtcDqFdeRKNlIKahriUkMs", "JvmwHCDtGgJJDXuLbpcbJLPSGYWPmKejKirP", "FCTdJYEfbipSGJXqmOfixwprwACALKfkwtvhpk", "fYXNDJgQNVTtXaOyXcgQkUVoRynfZsNEX", "xbZSlPsxDBxNbKsKQfaqpJUxOUXizbrDKDJWxYcsZn", "DyVEWMvNwdKscAbdbzGTjMovNqcvnRMwzlPFyuUbSXobLwOfRV", "BYvZTPCJqoWUCPeMDwWOUHenENgSWwAUlQRu", "ChkzCGvk", "xaMEojIiDoPeFoPCwqzHeRoEKZheCNTxefiAwffbOjhAHG", "LfqTPkqZiNdKOSrtOLLFqTjJH", "ZqugrYYDyfSPLwODjvVDpKVvWlmcbrZaKrglaa", "WyHCJeJlKlOfQIGkT", "qQJAblAecBELmdUmFHAIMLqueJBwHDrzyGKMMilsSBUjFEDkxD", "oKyOWJlRDVsNfjoRhIxXOPXbPCanQrQxMYMmgqaFTBcPgBkAbR", "TbuRnZvlggXOiiemTY", "gNbBMJYeYrCPPlLpuNwkbESrrnOxmzDBsCD", "WXRMGsQmAkWJkJBXiLMRXjrubeQAWXeSC", "tVulremTpITccPIhQUwYQzd", "PNxAqNSVgFUrhRyAuziaonrmCjEItMwsXMYCZLjcSUhLOaAQSk", "FenYRWwlTKt", "KMQFTPIeHTmqPRXFCNSTNcINWAXBDbPzthhHAMVNelZVFuFuum", "cdRDJKyuombZuRQMWzVUGTQtONc", "pxZPpzQwAXLBYojHNKydvVqATukqjpDcBEtJmODr", "na"}, 2)  );
		
		System.out.println( numberOfPictures(new String[]{"xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "xSLuhsfVpArQRckSMhTbgoDzGHZigtnDNpYzmaAPPpmFHpMTxS", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "UrJNiRbPZZKlQBcWsFYkLGXJVdR", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "vwytAzDUIPXuXdwkQbYPvZAINhfmxRcqutLfbhGoPXMCUQRUMw", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ", "FaagMzktDtpNSIfLMffKwflEbGCSfgUsLfguFSPRIefGiOvIZQ"}, 15)  );
    }
	
	public static int numberOfPictures(String[] labels, int k){
		int max = 0;
		Map<String, Integer> pics = new HashMap<String, Integer>();
		for(String label: labels){
			if(pics.get(label)!=null){
				pics.put(label, pics.get(label)+1);
			}else{
				pics.put(label,1);
			}
		}
		for(String key: pics.keySet()){
			int number = pics.get(key);
			max += Math.min(number, k-1);
		}
		
		return max;		
	}

}
